package binarysorttree.std01;

/**
 * 二叉排序数
 *  7 ，3，10，12，5，1，9 添加形成 二叉排序 然后用中序遍历 输出
 * @author yinb
 */
public class BinarySortTreeTest {
    public static void main(String[] args) {
        int arr[] = {7,3,10,12,5,1,9,2};
        BinarySortTree binarySortTree = new BinarySortTree();
        for (int i = 0; i < arr.length; i++) {
            Node node = new Node(arr[i]);
            binarySortTree.add(node);
        }
        binarySortTree.print();
//        binarySortTree.remove(4);
//        binarySortTree.remove(5);
        binarySortTree.remove(2);
        binarySortTree.remove(5);
        binarySortTree.remove(9);
        binarySortTree.remove(12);
        binarySortTree.remove(7);
        binarySortTree.remove(3);
        binarySortTree.remove(10);
        binarySortTree.remove(1);
        System.out.println();
        binarySortTree.print();
    }

    static  class  BinarySortTree{
        Node root;
        public void add(Node node){
            if(null == root){
                root = node;
            }else {
                root.add(node);
            }
        }

        /**
         * 查找要删除的key
         * @param date 目标值
         * @return 目标节点 没有为null
         */
        public Node findNode(int date){
            if(this.root == null){
                return null;
            }
            return this.root.findNode(date);
        }

        /**
         * 查找父节点
         * @param date 目标值
         * @return 父节点
         */
        public Node findParentNode(int date){
            if(this.root == null){
                return null;
            }
            return this.root.findParentNode(date);
        }

        /**
         * 中序遍历
         */
        public void print(){
            if(this.root == null){
                return;
            }
            this.root.printInorderTraversal(root);
        }

        /**
         * 删除节点
         * @param date 值
         * @return true 则删除成功
         */
        public int remove(int date){
            //找到对应的值 targetNode
            Node targetNode = this.findNode(date);
            //找到父节点 parentNode
            Node parentNode = this.root.findParentNode(date);
            //如果删没有 子节点 比如删 4 4 节点下
            if(targetNode.left == null && targetNode.right == null){
                if(parentNode!=null && parentNode.left!=null &&  parentNode.left.date == date ){
                    parentNode.left = null;
                    return 1;
                }else if(parentNode!=null && parentNode.right!=null && parentNode.right.date == date ){
                    parentNode.right = null;
                    return 1;
                }else if(parentNode == null && this.root.date == date){
                    this.root = null;
                    return 1;
                }
            }else if ( targetNode.left!=null && targetNode.right!=null){
                //双节点
                //找右边的树 最小的节点
                Node minRight = targetNode.right.findMinRight();
                remove(minRight.date);
                targetNode.date = minRight.date;
                return 1;
            }else {
                //单节点不为空
                //判断是父节点的左 还是右
                if( parentNode == null ){
                    this.root =  targetNode.left== null? targetNode.right:targetNode.left;
                    return 1;
                }else if( parentNode.right!=null && parentNode.right.date == targetNode.date ){
                    parentNode.right = targetNode.left== null? targetNode.right:targetNode.left;
                    return 1;
                }else if( parentNode.left!=null &&  parentNode.left.date == targetNode.date ){
                    parentNode.left = targetNode.left== null? targetNode.right:targetNode.left;
                    return 1;
                }
            }
            return 0;
        }
    }

   static class Node{
        int date;
        Node left;
        Node right;

        public Node(int date) {
            this.date = date;
        }

        public Node findMinRight(){
           if(this.left == null){
               return this;
           }else {
               return this.left.findMinRight();
           }
        }

       /**
        * 查找node
        * @param date
        * @return 节点
        */
        public Node findNode(int date){
            if(this.date>date){
                if(null != this.left){
                    //左子树
                    return this.left.findNode(date);
                }else {
                    return null;
                }
            }else if(this.date<date){
                if(null != this.right){
                    //右子树
                    return this.right.findNode(date);
                }else {
                    return null;
                }
            }else {
                return this;
            }
        }

       public Node findParentNode(int date){
            if( (this.left!=null && this.left.date ==date)
                    ||  (this.right!=null && this.right.date ==date) ){
                return this;
            }else {
                if(this.date < date && this.right!=null ){
                    return this.right.findParentNode(date);
                }else if(this.date > date && this.left!=null ) {
                    return this.left.findParentNode(date);
                }else {
                    return null;
                }
            }
       }



       /**
        *  如添加的节点的值 大于当前节点值 则放右子树 右子树为空 则this.right = node
        * @param node 添加的node
        */
        public void add(Node node){
            if(null == node){
                return;
            }
            // 右子树
            if(node.date > this.date){
                if(null == this.right){
                    this.right = node;
                }else {
                    this.right.add(node);
                }
            }else {
                if(null == this.left){
                    this.left = node;
                }else {
                    this.left.add(node);
                }
            }
        }
        //中序遍历 左 根 右
        public void printInorderTraversal(Node node){
            if(null != node.left){
                printInorderTraversal(node.left);
            }
            System.out.print(node.date + "   ");
            if(null != node.right){
                printInorderTraversal(node.right);
            }
        }
    }
}
